﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution110
    {
        public bool IsBalanced1(TreeNode root)//前序遍历，自上而下
        {
            if (root == null) return true;

            int depthL = Depth(root.left);
            int depthR = Depth(root.right);
            if (depthL - depthR > 1 || depthR - depthL > 1)
            {
                return false;
            }
            else
            {
                return IsBalanced(root.left) && IsBalanced(root.right);
            }
        }

        private int Depth(TreeNode root)
        {
            if (root == null) return 0;

            int depthL = Depth(root.left);
            int depthR = Depth(root.right);
            return Math.Max(depthL, depthR) + 1;
        }

        public bool IsBalanced(TreeNode root)//后序遍历，自底向上
        {
            return Height(root) >= 0;//高度差不为-1，就平衡
        }

        private int Height(TreeNode root)
        {
            if (root == null) return 0;
            int depthL = Height(root.left);
            int depthR = Height(root.right);
            if (depthL == -1 || depthR == -1 || Math.Abs(depthR - depthL) > 1)
            {
                return -1;//孩子不平衡，自己也不平衡
            }
            else
            {
                return Math.Max(depthL, depthR) + 1;
            }
        }
    }
}